package codeRandomThoughts.Test37解数独;

public class Solution {

    //建立两个二维数组记录横向与竖向的used数组 H:Horizon V:Vertical
    boolean[][] usedV = new boolean[9][10];
    boolean[][] usedH = new boolean[9][10];

    //建立一个二维数组记录每个九宫格内的数字是否使用过
    boolean[][] used9x9 = new boolean[9][10];

    //记录数独中当前有多少个空白格
    int blank = 0;

    //更新used数组
    public void updateUsed(int num, int row, int column, boolean flag) {
        usedH[row][num] = flag;
        usedV[column][num] = flag;

        //更新九宫格比较特殊,要计算当前坐标在第几个九宫格中
        //0 1 2
        //3 4 5
        //6 7 8
        used9x9[getIndex(row, column)][num] = flag;
    }

    //根据行号与列号返回其对应的九宫格下标
    //0 1 2
    //3 4 5
    //6 7 8
    public int getIndex(int row, int column) {
        //这里自己动脑子想一想,举个例子就明白了
        return (row / 3) * 3 + column / 3;
    }

    //把所有用过的数字都记录一遍,即初始化三个used数组
    public void initUsed(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    updateUsed(num, i, j, true);
                } else {
                    //记录数独中有几个空位,回溯函数的终止条件要用
                    blank++;
                }
            }
        }
    }

    //判断当前位置上的数字是否在used数组中出现过
    public boolean isValid(int num, int row, int column) {
        return (!usedV[column][num] && !usedH[row][num] && !used9x9[getIndex(row, column)][num]);
    }

    //主函数
    public void solveSudoku(char[][] board) {
        initUsed(board);
        backtracking(board, 0, 0);
    }

    //回溯函数
    public void backtracking(char[][] board, int row, int column) {
        //终止条件
        if (blank == 0) {
            return;
        }

        //单层搜索逻辑
        //首先检查当前遍历到的格子是否为空
        if (board[row][column] == '.') {
            //横向遍历,尝试往里面塞入1-9
            for (int num = 1; num <= 9; num++) {
                if (isValid(num, row, column)) {
                    //塞入的数字合法,就遍历下一个格子
                    board[row][column] = (char) (num + '0');
                    blank--;
                    updateUsed(num, row, column, true);
                    //这里简写了,仔细观察可以看出这里是模仿矩阵遍历的操作
                    backtracking(board, (column + 1) / 9 + row, (column + 1) % 9);
                    if (blank == 0) {
                        //如果递归完毕发现全部填满了,那就不用回溯了,直接return
                        return;
                    }
                    //回溯
                    updateUsed(num, row, column, false);
                    blank++;
                    board[row][column] = '.';
                }
            }
        } else {
            //如果当前格子不为空,直接遍历下一个格子
            backtracking(board, (column + 1) / 9 + row, (column + 1) % 9);
        }
    }


}
